package problema243;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;


public class Resilence {
	
	static double a = 15499, b = 94744, res = a / b;
	static boolean[] isPrime;
	static Set<Integer> primos = new HashSet<Integer>();
	
	public static void main(String[] args){
		sieveOfEratosthenes(100000);
		System.out.println(totient(7));
		//System.out.println(minRes());
	}
	
	public static int minRes(){
		sieveOfEratosthenes(100000000);
		int act = 94745, cant;
		double div = 0;
		
		return act;
	}
	
	public static double totient(int n){
		double res = (double) n, act = 0;
		Iterator<Integer> it = primos.iterator();
		Integer actIt = 0;
		while(it.hasNext()){
			actIt = it.next();
			if(actIt > n) break;
			if((n % actIt) == 0){
				act = (double) 1 - ((double)1 / (double)actIt);
				res *= act;
			}
		}
		return res;
	}
	
	
	public static int coprimos(int n){
		int cant = 0;
		for(int i = 1; i < n; i++){
			if(gcd(i,n) == 1) cant++;
		}
		return cant;
	}
	
	public static int gcd(int p, int q) {
        if (q == 0) return p;
        if (p == 0) return q;

        // p and q even
        if ((p & 1) == 0 && (q & 1) == 0) return gcd(p >> 1, q >> 1) << 1;

        // p is even, q is odd
        else if ((p & 1) == 0) return gcd(p >> 1, q);

        // p is odd, q is even
        else if ((q & 1) == 0) return gcd(p, q >> 1);

        // p and q odd, p >= q
        else if (p >= q) return gcd((p-q) >> 1, q);

        // p and q odd, p < q
        else return gcd(p, (q-p) >> 1);
    }
	
	public static int GCD(int a, int b) {
		   if (b == 0) return a;
		   return GCD(b, a % b);
	}
	
	public static List<Integer> primeFactors(int numero) {
	    int n = numero;
	    List<Integer> factores = new ArrayList<Integer>();
	    for (int i = 2; i <= n; i++) {
	      while (n % i == 0) {
	        factores.add(i);
	        n /= i;
	      }
	    }
	    return factores;
	  }
	
	public static void sieveOfEratosthenes(int n){
	     isPrime = new boolean[n + 1];
	     for (int i = 2; i <= n; i++) {
	         isPrime[i] = true;
	     }
	     for (int i = 2; i*i <= n; i++) {
	         if (isPrime[i]) {
	             for (int j = i; i*j <= n; j++) {
	                 isPrime[i*j] = false;
	             }
	         }
	     }
	     for(int i = 0; i < isPrime.length; i++){
	    	 if(isPrime[i]) primos.add(i);
	     }
	 }

}
